징검다리 건너기

문제

요약하자면 k 길이의 부분배열의 최댓값의 최솟값을 구하는 문제이다

거의 비슷한 leetcode 문제가 있다
Sliding Window Maximum

처음 시도

슬라이딩으로 배열 다음 값을 구간 최대값과 비교하고, 맨 앞 값을 최대값과 비교해서 최댓값이 맨앞이면 다시 구간 최댓값을 구하는 방식으로 풀었다

function solution(stones, k) {
    var answer = 0;
    const len=stones.length
    if(len==k){
        return Math.min(...stones)
    }
    let curMax=Math.max(...stones.slice(0,k))
    answer=curMax
    for(let i=k;i<len;i++){
        if(stones[i-k]==curMax){
            curMax=Math.max(...stones.slice(i-k+1,i))
        }
        curMax=Math.max(curMax,stones[i])
        answer=Math.min(answer,curMax)
    }
    return answer;
}

문제는 배열이 [6, 5, 4, 3, 2, 1] 처럼 계단식 하락일 경우 매 경우 마다 Math.max를 실행해서 시간복잡도가 높아질 수 있다.(최악의 경우 O(n**3))

개선된 방법

슬라이딩을 살짝 변형하는 방법이 있다
새로 추가되는 값을 input, 나가는 값을 out 이라고 할 때

1. Input 값보다 앞에 있으면서 작은 값은 생략될 수 있다.
2. 생략되지 않고 out 되는 값은 부분배열에서 최댓값이다

이렇게 하면 O(n) 정도의 시간복잡도를 가진다

function solution(stones, k) {
    var answer = 0;
    const len=stones.length
    if(len==k){
        return Math.min(...stones)
    }
    let curMax=Math.max(...stones.slice(0,k))
    answer=curMax
    for(let i=k;i<len;i++){
        if(stones[i-k]==curMax){
            curMax=Math.max(...stones.slice(i-k+1,i))
        }
        curMax=Math.max(curMax,stones[i])
        answer=Math.min(answer,curMax)
    }
    return answer;
}